Overview
In this assessment we aim to use the MACCDC conn data to perform data analysis and modelling. We first must import the data.
mydata <- read.csv("MAC.csv")
mydata <- data.frame(mydata)
mydata
We first want to look for missing data. Service, duration, orig_bytes, resp_bytes and local_orig all seem to have missing data in them so we will see what percentage.
mtab0=data.frame(
missingduration=is.na(mydata[,"duration"]),
proto=mydata[,"proto"])
mtab0=table(mtab0)
(apply(mtab0,2,function(x)x/sum(x)))
proto
missingduration icmp tcp udp
FALSE 0.8585338 0.1656118 0.3089144
TRUE 0.1414662 0.8343882 0.6910856
mtab1=data.frame(
missing_orig_bytes=is.na(mydata[,"orig_bytes"]),
proto=mydata[,"proto"])
mtab1=table(mtab1)
(apply(mtab1,2,function(x)x/sum(x)))
proto
missing_orig_bytes icmp tcp udp
FALSE 0.8585338 0.1656118 0.3089144
TRUE 0.1414662 0.8343882 0.6910856
mtab2=data.frame(
missing_resp_bytes=is.na(mydata[,"resp_bytes"]),
proto=mydata[,"proto"])
mtab2=table(mtab2)
(apply(mtab2,2,function(x)x/sum(x)))
proto
missing_resp_bytes icmp tcp udp
FALSE 0.8585338 0.1656118 0.3089144
TRUE 0.1414662 0.8343882 0.6910856
mtab3=data.frame(
missing_local_orig=is.na(mydata[,"local_orig"]),
proto=mydata[,"proto"])
mtab3=table(mtab3)
(apply(mtab3,2,function(x)x/sum(x)))
icmp tcp udp
1 1 1
Thus we are missing the local_orig feature for every data point in the data set. We may then consider dropping this entire column as it serves no use to us and we cannot impute the data without prior knowledge of the data set and what it should look like. The duration, orig_bytes and resp_bytes all appear to be missing exactly the same data - on further analysis, we see that whenever one is missing, all three are missing.
Some initial data cleansing will come from removing the X column and the ts column. The X column is produced by the sampling and since we have a random sample of the data, the ts provides no real information on the data.
unique_uid <- mydata[!duplicated(mydata[,c('uid')]),]
unique_uid
Thus all our uid’s are unique and therefore wont provide us with any extra information either since they will be uncorrelated with the rest of the data. This is the only column with this trait, and all other columns have values which occur more than once so we can drop the uid column too.
drop_columns <- c("X","ts","local_orig","uid")
mydata <- mydata[, !names(mydata) %in% drop_columns]
head(mydata)
So we have removed the columns that didn’t provide us with any extra information. We will now extract the data we will use for DBSCAN to create clusters. The following code is pulled from Alex’s workbook and allows us to pull out 7 of the features to use for DBSCAN and ensures all elements are numeric.
miss.me <- vector(length = nrow(mydata))
miss.me <- rep(0, times = nrow(mydata))
for(i in 1:nrow(mydata)) {
if(is.na(mydata$duration[i])) { miss.me[i] <- 1 }
}
str(mydata)
'data.frame': 226943 obs. of 16 variables:
$ id.orig_h : chr "192.168.202.110" "192.168.202.83" "192.168.202.110" "192.168.202.138" ...
$ id.orig_p : int 50427 46442 12662 35203 63958 39436 52132 41741 40224 63022 ...
$ id.resp_h : chr "192.168.22.102" "192.168.206.44" "192.168.22.1" "192.168.24.187" ...
$ id.resp_p : int 15457 42 17800 10629 56587 33384 32776 7476 1688 2010 ...
$ proto : chr "tcp" "tcp" "tcp" "tcp" ...
$ service : chr "-" "-" "-" "-" ...
$ duration : num NA NA NA NA NA NA NA NA NA NA ...
$ orig_bytes : int NA NA NA NA NA NA NA NA NA NA ...
$ resp_bytes : int NA NA NA NA NA NA NA NA NA NA ...
$ conn_state : chr "REJ" "REJ" "S0" "S0" ...
$ missed_bytes : int 0 0 0 0 0 0 0 0 0 0 ...
$ history : chr "Sr" "Sr" "S" "S" ...
$ orig_pkts : int 1 1 1 1 1 1 1 1 1 1 ...
$ orig_ip_bytes: int 48 60 48 44 48 44 60 60 60 44 ...
$ resp_pkts : int 1 1 0 0 0 1 1 0 1 0 ...
$ resp_ip_bytes: int 40 40 0 0 0 40 40 0 40 0 ...
mydata.good <- as.data.frame(cbind(id.orig_p = mydata$id.orig_p, id.resp_p = mydata$id.resp_p,
orig_pkts = mydata$orig_pkts, orig_ip_bytes = mydata$orig_ip_bytes,
resp_pkts = mydata$resp_pkts, resp_ip_bytes = mydata$resp_ip_bytes))
mydata.good<- cbind(mydata.good, miss.me)
head(mydata.good)
str(mydata.good) # Should be only ints and nums
'data.frame': 226943 obs. of 7 variables:
$ id.orig_p : int 50427 46442 12662 35203 63958 39436 52132 41741 40224 63022 ...
$ id.resp_p : int 15457 42 17800 10629 56587 33384 32776 7476 1688 2010 ...
$ orig_pkts : int 1 1 1 1 1 1 1 1 1 1 ...
$ orig_ip_bytes: int 48 60 48 44 48 44 60 60 60 44 ...
$ resp_pkts : int 1 1 0 0 0 1 1 0 1 0 ...
$ resp_ip_bytes: int 40 40 0 0 0 40 40 0 40 0 ...
$ miss.me : num 1 1 1 1 1 1 1 1 1 1 ...
for(i in 1:ncol(mydata.good)) { mydata.good[,i] <- as.numeric(mydata.good[,i]) }
str(mydata.good) ## All should be nums now
'data.frame': 226943 obs. of 7 variables:
$ id.orig_p : num 50427 46442 12662 35203 63958 ...
$ id.resp_p : num 15457 42 17800 10629 56587 ...
$ orig_pkts : num 1 1 1 1 1 1 1 1 1 1 ...
$ orig_ip_bytes: num 48 60 48 44 48 44 60 60 60 44 ...
$ resp_pkts : num 1 1 0 0 0 1 1 0 1 0 ...
$ resp_ip_bytes: num 40 40 0 0 0 40 40 0 40 0 ...
$ miss.me : num 1 1 1 1 1 1 1 1 1 1 ...
# sum(mydata.good$miss.me)/nrow(mydata.good) ## 82.7% missing
I dont want to drop any data that may be important so I’ll also use the protocol, connection state and history features in my analysis.
proto <- as.factor(c(mydata$proto))
proto <- unclass(proto)
conn_state <- as.factor(c(mydata$conn_state))
conn_state <- unclass(conn_state)
history <- as.factor(c(mydata$history))
history <- unclass(history)
mydata.good$proto <- proto
mydata.good$conn_state <- conn_state
mydata.good$history <- history
mydata.good
## We'll do 10-fold CV and then apply DBSCAN, training on 90%
dg <- mydata.good
ran <- sample(1:nrow(dg), 0.9 * nrow(dg))
nor <-function(x) { (x -min(x))/(max(x)-min(x)) }
dg_norm <- as.data.frame(lapply(dg, nor))
# head(dg_norm)
dg_train <- dg_norm[ran,] ## extract training set
dg_test <- dg_norm[-ran,] ## extract testing set
dg_target_cat <- dg[ran, ncol(dg)]
dg_test_cat <- dg[-ran, ncol(dg)]
SVD
Now we can look at running DBSCAN on our data. We first need to perform PCA to figure out how many principle components to use in DBSCAN.
library("dbscan")
dg_train.svd <- svd(dg_train)
plot(dg_train.svd$d,xlab="Eigenvalue index",ylab="Eigenvalue",log="y")

plot(dg_train.svd$d,xlab="Eigenvalue index",ylab="Eigenvalue")

Plotting with a log y-axis and a normal y-axis give strikingly different results. The first eigenvector explains most of the variance and the 5 after that seeming explain almost the same amount of variance between them as the first one. I don’t think using just the first eigenvalue would provide that much insight and therefore will use 6 of them (this is still reducing dimensionality by almost half).
npcs = 6
We now plot the PCA to visualise the clusters formed here. We’re not plotting according to any categorical data i.e. normal vs non-normal so we may not get that much information from this.
i=1;j=2
plot(dg_train.svd$u[,i],
dg_train.svd$u[,j],type="p",
col="#33333311",pch=16,cex=1)

Finding Parameters for DBSCAN
Eps specifies how close the points should be to each other to form a cluster. If the distance is less than eps, they are considered neighbours. We find this number by finding the ‘knee’ in the plot below. I have chosen to use 7 neighbours here.
test=kNNdist(dg_train.svd$u[,1:npcs], k = 7,all=TRUE)
testmin=apply(test,1,min)
plot(sort(testmin[testmin>1e-8]),log="y")
threshholds= c(0.01,0.001,0.0001,0.00001,0.000001)
abline(h=c(0.01,0.001,0.0001,0.00001,0.000001))
abline(h=0.0001, col="red")

So we choose h=0.0001 as our limit since this allows us to capture most of the information here. We also need to define our minimum number of points to form a cluster. The recommendation is to use minPts = 2*dim for large data sets to ensure we find significant clusters and avoid noise so this is what we shall choose.
##DBSCAN
Now we finally perform DBSCAN.
minPts = c(20, 25, 30, 35, 40, 45, 50, 75, 100, 125, 150, 175, 200, 225, 250)
clustercounts = c()
for(val in minPts) {
dbscanres = dbscan(dg_train.svd$u[,1:6],eps = 0.0001,minPts = val)
clustercounts[val] <- (length(unique(dbscanres$cluster)))
}
clustercounts
[1] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 209 NA
[22] NA NA NA 143 NA NA NA NA 157 NA NA NA NA 136 NA NA NA NA 110 NA NA
[43] NA NA 99 NA NA NA NA 111 NA NA NA NA NA NA NA NA NA NA NA NA NA
[64] NA NA NA NA NA NA NA NA NA NA NA 98 NA NA NA NA NA NA NA NA NA
[85] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 85 NA NA NA NA NA
[106] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 40 NA
[127] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[148] NA NA 25 NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[169] NA NA NA NA NA NA 17 NA NA NA NA NA NA NA NA NA NA NA NA NA NA
[190] NA NA NA NA NA NA NA NA NA NA 22 NA NA NA NA NA NA NA NA NA NA
[211] NA NA NA NA NA NA NA NA NA NA NA NA NA NA 21 NA NA NA NA NA NA
[232] NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA NA 24
Thus we seem to hit some limiting value at 175 since a minPts of 200 has a higher amount of clusters than a minPts of 175. Since we want ou data to be interpretable we may look at reducing the amount of clusters and therefore the noise. Thus we will use an initial minPts of 175.
The output we get from this isn’t very insightful though and leaves a lot to be desired.
dbscan175 = dbscan(dg_train.svd$u[,1:6],eps = 0.0001,minPts = 175)
dbscan50 = dbscan(dg_train.svd$u[,1:6],eps=0.0001,minPts = 50)
dbscan30 = dbscan(dg_train.svd$u[,1:6],eps=0.0001,minPts = 30)
library(cluster)
# trying to calculate the silhouette score of this clustering to see if its valid or not - currently reports Error: Vector memory exhausted (limit reached?) - I've tried looking into work arounds but cant get anything working so I'll leave this for now.
#ss <- silhouette(dbscanres$cluster, dist(dg_train.svd$u))
Plotting resulting clusters
for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan175$cluster+1],pch=19,cex=0.5)
par(new=TRUE)
}
}

for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan50$cluster+1],pch=19,cex=0.5)
par(new=TRUE)
}
}

for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan30$cluster+1],pch=19,cex=0.5)
par(new=TRUE)
}
}

for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan175$cluster+1],pch=19,cex=0.5)
}
}















for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan50$cluster+1],pch=19,cex=0.5)
}
}















for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan30$cluster+1],pch=19,cex=0.5)
}
}















jpeg("Assessment2 DBSCAN Clustering.jpg")
for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab="",
ylab="",
col=c("#66666666",rainbow(41))[dbscan30$cluster+1],pch=19,cex=0.5)
par(new=TRUE)
}
}
jpeg("Assessment2 DBSCAN Clustering Eigenvector split.jpg")
op <- par(mfrow=c(5,3))
for (k in 1:5){
a = seq(k+1,6)
for (l in a){
if(k==l){next}
plot(dg_train.svd$u[,k],
dg_train.svd$u[,l],xlab=k,
ylab=l,
col=c("#66666666",rainbow(41))[dbscan30$cluster+1],pch=19,cex=0.5)
}
}
par(op)
dev.off()
null device
1
dg_train.clustered <- data.frame(dg_train)
dg_train.clustered$cluster <- dbscan175$cluster
dg_train.clustered
M matrix
Now we look at the M matrix produced by Alex that is a sparse matrix showing connections between origin IP’s and response IP’s.
library(Matrix)
library(irlba)
library(Rtsne)
So1 <- tapply(mydata$id.orig_h, mydata$id.orig_h)
De1 <- tapply(mydata$id.resp_h, mydata$id.resp_h)
Est <- as.matrix(cbind(So1, De1))
M<- sparseMatrix(i=Est[,1], j=Est[,2])
M.svd = svd(M)
plot(M.svd$d,xlab="Eigenvalue index",ylab="Eigenvalue",log="y")

plot(M.svd$d,xlab="Eigenvalue index",ylab="Eigenvalue")

From the log axis it looks like we need the first ~100 eigenvalues but using the normal plot, it looks like we an get away with using ~30.
npcsM = 30
testM=kNNdist(M.svd$u[,1:npcsM], k = 7,all=TRUE)
testminM=apply(testM,1,min)
plot(sort(testminM[testminM>1e-15]),log="y")
threshholds= c(0.1,0.01,0.001,0.0001,0.00001,0.000001)
abline(h=c(0.01,0.001,0.0001,0.00001,0.000001))
abline(h=0.5, col="red")

It looks like we want eps = 0.5 although we dont seem to get a knee in the data so it’s hard to pinpoint this.
MminPts = c(20, 50, 200)
clustercountsM = c()
for(val in MminPts) {
dbscanresM = dbscan(dg_train.svd$u[,1:6],eps = 0.5,minPts = val)
clustercountsM[val] <- (length(unique(dbscanresM$cluster)))
}
References:
Data from SecRepo
Converting categorical variables
Adding columns to data frames
Finding Unique Values
DBSCAN on flowers
Saving Plots
DBSCAN Parameter Estimation
Finding the knee in kNNDist
Silhouette Score introduction
Error with silhouette score
Silhouette Function
LS0tCnRpdGxlOiAiQXNzZXNzbWVudCAyIC0gTWF0dCIKb3V0cHV0OgogIGh0bWxfbm90ZWJvb2s6IGRlZmF1bHQKLS0tCiMgT3ZlcnZpZXcKSW4gdGhpcyBhc3Nlc3NtZW50IHdlIGFpbSB0byB1c2UgdGhlIE1BQ0NEQyBjb25uIGRhdGEgdG8gcGVyZm9ybSBkYXRhIGFuYWx5c2lzIGFuZCBtb2RlbGxpbmcuIFdlIGZpcnN0IG11c3QgaW1wb3J0IHRoZSBkYXRhLgoKYGBge3J9Cm15ZGF0YSA8LSByZWFkLmNzdigiTUFDLmNzdiIpCm15ZGF0YSA8LSBkYXRhLmZyYW1lKG15ZGF0YSkKYGBgCgpgYGB7cn0KbXlkYXRhCmBgYApXZSBmaXJzdCB3YW50IHRvIGxvb2sgZm9yIG1pc3NpbmcgZGF0YS4gU2VydmljZSwgZHVyYXRpb24sIG9yaWdfYnl0ZXMsIHJlc3BfYnl0ZXMgYW5kIGxvY2FsX29yaWcgYWxsIHNlZW0gdG8gaGF2ZSBtaXNzaW5nIGRhdGEgaW4gdGhlbSBzbyB3ZSB3aWxsIHNlZSB3aGF0IHBlcmNlbnRhZ2UuCgpgYGB7cn0KbXRhYjA9ZGF0YS5mcmFtZSgKICAgIG1pc3NpbmdkdXJhdGlvbj1pcy5uYShteWRhdGFbLCJkdXJhdGlvbiJdKSwKICAgIHByb3RvPW15ZGF0YVssInByb3RvIl0pCm10YWIwPXRhYmxlKG10YWIwKQooYXBwbHkobXRhYjAsMixmdW5jdGlvbih4KXgvc3VtKHgpKSkKCm10YWIxPWRhdGEuZnJhbWUoCiAgICBtaXNzaW5nX29yaWdfYnl0ZXM9aXMubmEobXlkYXRhWywib3JpZ19ieXRlcyJdKSwKICAgIHByb3RvPW15ZGF0YVssInByb3RvIl0pCm10YWIxPXRhYmxlKG10YWIxKQooYXBwbHkobXRhYjEsMixmdW5jdGlvbih4KXgvc3VtKHgpKSkKCm10YWIyPWRhdGEuZnJhbWUoCiAgICBtaXNzaW5nX3Jlc3BfYnl0ZXM9aXMubmEobXlkYXRhWywicmVzcF9ieXRlcyJdKSwKICAgIHByb3RvPW15ZGF0YVssInByb3RvIl0pCm10YWIyPXRhYmxlKG10YWIyKQooYXBwbHkobXRhYjIsMixmdW5jdGlvbih4KXgvc3VtKHgpKSkKCm10YWIzPWRhdGEuZnJhbWUoCiAgICBtaXNzaW5nX2xvY2FsX29yaWc9aXMubmEobXlkYXRhWywibG9jYWxfb3JpZyJdKSwKICAgIHByb3RvPW15ZGF0YVssInByb3RvIl0pCm10YWIzPXRhYmxlKG10YWIzKQooYXBwbHkobXRhYjMsMixmdW5jdGlvbih4KXgvc3VtKHgpKSkKYGBgClRodXMgd2UgYXJlIG1pc3NpbmcgdGhlIGxvY2FsX29yaWcgZmVhdHVyZSBmb3IgZXZlcnkgZGF0YSBwb2ludCBpbiB0aGUgZGF0YSBzZXQuIFdlIG1heSB0aGVuIGNvbnNpZGVyIGRyb3BwaW5nIHRoaXMgZW50aXJlIGNvbHVtbiBhcyBpdCBzZXJ2ZXMgbm8gdXNlIHRvIHVzIGFuZCB3ZSBjYW5ub3QgaW1wdXRlIHRoZSBkYXRhIHdpdGhvdXQgcHJpb3Iga25vd2xlZGdlIG9mIHRoZSBkYXRhIHNldCBhbmQgd2hhdCBpdCBzaG91bGQgbG9vayBsaWtlLiBUaGUgZHVyYXRpb24sIG9yaWdfYnl0ZXMgYW5kIHJlc3BfYnl0ZXMgYWxsIGFwcGVhciB0byBiZSBtaXNzaW5nIGV4YWN0bHkgdGhlIHNhbWUgZGF0YSAtIG9uIGZ1cnRoZXIgYW5hbHlzaXMsIHdlIHNlZSB0aGF0IHdoZW5ldmVyIG9uZSBpcyBtaXNzaW5nLCBhbGwgdGhyZWUgYXJlIG1pc3NpbmcuIAoKU29tZSBpbml0aWFsIGRhdGEgY2xlYW5zaW5nIHdpbGwgY29tZSBmcm9tIHJlbW92aW5nIHRoZSBYIGNvbHVtbiBhbmQgdGhlIHRzIGNvbHVtbi4gVGhlIFggY29sdW1uIGlzIHByb2R1Y2VkIGJ5IHRoZSBzYW1wbGluZyBhbmQgc2luY2Ugd2UgaGF2ZSBhIHJhbmRvbSBzYW1wbGUgb2YgdGhlIGRhdGEsIHRoZSB0cyBwcm92aWRlcyBubyByZWFsIGluZm9ybWF0aW9uIG9uIHRoZSBkYXRhLgoKYGBge3J9CnVuaXF1ZV91aWQgPC0gbXlkYXRhWyFkdXBsaWNhdGVkKG15ZGF0YVssYygndWlkJyldKSxdCnVuaXF1ZV91aWQKYGBgClRodXMgYWxsIG91ciB1aWQncyBhcmUgdW5pcXVlIGFuZCB0aGVyZWZvcmUgd29udCBwcm92aWRlIHVzIHdpdGggYW55IGV4dHJhIGluZm9ybWF0aW9uIGVpdGhlciBzaW5jZSB0aGV5IHdpbGwgYmUgdW5jb3JyZWxhdGVkIHdpdGggdGhlIHJlc3Qgb2YgdGhlIGRhdGEuIFRoaXMgaXMgdGhlIG9ubHkgY29sdW1uIHdpdGggdGhpcyB0cmFpdCwgYW5kIGFsbCBvdGhlciBjb2x1bW5zIGhhdmUgdmFsdWVzIHdoaWNoIG9jY3VyIG1vcmUgdGhhbiBvbmNlIHNvIHdlIGNhbiBkcm9wIHRoZSB1aWQgY29sdW1uIHRvby4KCmBgYHtyfQpkcm9wX2NvbHVtbnMgPC0gYygiWCIsInRzIiwibG9jYWxfb3JpZyIsInVpZCIpCm15ZGF0YSA8LSBteWRhdGFbLCAhbmFtZXMobXlkYXRhKSAlaW4lIGRyb3BfY29sdW1uc10KYGBgCgpgYGB7cn0KaGVhZChteWRhdGEpCmBgYAoKU28gd2UgaGF2ZSByZW1vdmVkIHRoZSBjb2x1bW5zIHRoYXQgZGlkbid0IHByb3ZpZGUgdXMgd2l0aCBhbnkgZXh0cmEgaW5mb3JtYXRpb24uIFdlIHdpbGwgbm93IGV4dHJhY3QgdGhlIGRhdGEgd2Ugd2lsbCB1c2UgZm9yIERCU0NBTiB0byBjcmVhdGUgY2x1c3RlcnMuIFRoZSBmb2xsb3dpbmcgY29kZSBpcyBwdWxsZWQgZnJvbSBBbGV4J3Mgd29ya2Jvb2sgYW5kIGFsbG93cyB1cyB0byBwdWxsIG91dCA3IG9mIHRoZSBmZWF0dXJlcyB0byB1c2UgZm9yIERCU0NBTiBhbmQgZW5zdXJlcyBhbGwgZWxlbWVudHMgYXJlIG51bWVyaWMuCgpgYGB7cn0KbWlzcy5tZSA8LSB2ZWN0b3IobGVuZ3RoID0gbnJvdyhteWRhdGEpKQptaXNzLm1lIDwtIHJlcCgwLCB0aW1lcyA9IG5yb3cobXlkYXRhKSkKZm9yKGkgaW4gMTpucm93KG15ZGF0YSkpIHsKCWlmKGlzLm5hKG15ZGF0YSRkdXJhdGlvbltpXSkpIHsgbWlzcy5tZVtpXSA8LSAxIH0KCX0Kc3RyKG15ZGF0YSkKbXlkYXRhLmdvb2QgPC0gYXMuZGF0YS5mcmFtZShjYmluZChpZC5vcmlnX3AgPSBteWRhdGEkaWQub3JpZ19wLCBpZC5yZXNwX3AgPSBteWRhdGEkaWQucmVzcF9wLCAKb3JpZ19wa3RzID0gbXlkYXRhJG9yaWdfcGt0cywgb3JpZ19pcF9ieXRlcyA9IG15ZGF0YSRvcmlnX2lwX2J5dGVzLCAKcmVzcF9wa3RzID0gbXlkYXRhJHJlc3BfcGt0cywgcmVzcF9pcF9ieXRlcyA9IG15ZGF0YSRyZXNwX2lwX2J5dGVzKSkKbXlkYXRhLmdvb2Q8LSBjYmluZChteWRhdGEuZ29vZCwgbWlzcy5tZSkKaGVhZChteWRhdGEuZ29vZCkKc3RyKG15ZGF0YS5nb29kKSAjIFNob3VsZCBiZSBvbmx5IGludHMgYW5kIG51bXMKCmZvcihpIGluIDE6bmNvbChteWRhdGEuZ29vZCkpIHsgbXlkYXRhLmdvb2RbLGldIDwtIGFzLm51bWVyaWMobXlkYXRhLmdvb2RbLGldKSB9CnN0cihteWRhdGEuZ29vZCkJCSMjIEFsbCBzaG91bGQgYmUgbnVtcyBub3cKIyBzdW0obXlkYXRhLmdvb2QkbWlzcy5tZSkvbnJvdyhteWRhdGEuZ29vZCkgIyMgODIuNyUgbWlzc2luZwoKYGBgCgpJIGRvbnQgd2FudCB0byBkcm9wIGFueSBkYXRhIHRoYXQgbWF5IGJlIGltcG9ydGFudCBzbyBJJ2xsIGFsc28gdXNlIHRoZSBwcm90b2NvbCwgY29ubmVjdGlvbiBzdGF0ZSBhbmQgaGlzdG9yeSBmZWF0dXJlcyBpbiBteSBhbmFseXNpcy4KYGBge3J9CnByb3RvIDwtIGFzLmZhY3RvcihjKG15ZGF0YSRwcm90bykpCnByb3RvIDwtIHVuY2xhc3MocHJvdG8pCgpjb25uX3N0YXRlIDwtIGFzLmZhY3RvcihjKG15ZGF0YSRjb25uX3N0YXRlKSkKY29ubl9zdGF0ZSA8LSB1bmNsYXNzKGNvbm5fc3RhdGUpCgpoaXN0b3J5IDwtIGFzLmZhY3RvcihjKG15ZGF0YSRoaXN0b3J5KSkKaGlzdG9yeSA8LSB1bmNsYXNzKGhpc3RvcnkpCgpteWRhdGEuZ29vZCRwcm90byA8LSBwcm90bwpteWRhdGEuZ29vZCRjb25uX3N0YXRlIDwtIGNvbm5fc3RhdGUKbXlkYXRhLmdvb2QkaGlzdG9yeSA8LSBoaXN0b3J5CgpteWRhdGEuZ29vZApgYGAKCmBgYHtyfQoJIyMgV2UnbGwgZG8gMTAtZm9sZCBDViBhbmQgdGhlbiBhcHBseSBEQlNDQU4sIHRyYWluaW5nIG9uIDkwJQpkZyA8LSBteWRhdGEuZ29vZApyYW4gPC0gc2FtcGxlKDE6bnJvdyhkZyksIDAuOSAqIG5yb3coZGcpKQpub3IgPC1mdW5jdGlvbih4KSB7ICh4IC1taW4oeCkpLyhtYXgoeCktbWluKHgpKSAgIH0KZGdfbm9ybSA8LSBhcy5kYXRhLmZyYW1lKGxhcHBseShkZywgbm9yKSkKCSMgaGVhZChkZ19ub3JtKQoKZGdfdHJhaW4gPC0gZGdfbm9ybVtyYW4sXSAJIyMgZXh0cmFjdCB0cmFpbmluZyBzZXQKZGdfdGVzdCA8LSBkZ19ub3JtWy1yYW4sXSAgIAkjIyBleHRyYWN0IHRlc3Rpbmcgc2V0CmRnX3RhcmdldF9jYXQgPC0gZGdbcmFuLCBuY29sKGRnKV0KZGdfdGVzdF9jYXQgPC0gZGdbLXJhbiwgbmNvbChkZyldCmBgYAoKIyMgU1ZECgpOb3cgd2UgY2FuIGxvb2sgYXQgcnVubmluZyBEQlNDQU4gb24gb3VyIGRhdGEuIFdlIGZpcnN0IG5lZWQgdG8gcGVyZm9ybSBQQ0EgdG8gZmlndXJlIG91dCBob3cgbWFueSBwcmluY2lwbGUgY29tcG9uZW50cyB0byB1c2UgaW4gREJTQ0FOLgoKYGBge3J9CmxpYnJhcnkoImRic2NhbiIpCmBgYAoKYGBge3J9CmRnX3RyYWluLnN2ZCA8LSBzdmQoZGdfdHJhaW4pCmBgYAoKYGBge3J9CnBsb3QoZGdfdHJhaW4uc3ZkJGQseGxhYj0iRWlnZW52YWx1ZSBpbmRleCIseWxhYj0iRWlnZW52YWx1ZSIsbG9nPSJ5IikKcGxvdChkZ190cmFpbi5zdmQkZCx4bGFiPSJFaWdlbnZhbHVlIGluZGV4Iix5bGFiPSJFaWdlbnZhbHVlIikKYGBgClBsb3R0aW5nIHdpdGggYSBsb2cgeS1heGlzIGFuZCBhIG5vcm1hbCB5LWF4aXMgZ2l2ZSBzdHJpa2luZ2x5IGRpZmZlcmVudCByZXN1bHRzLiBUaGUgZmlyc3QgZWlnZW52ZWN0b3IgZXhwbGFpbnMgbW9zdCBvZiB0aGUgdmFyaWFuY2UgYW5kIHRoZSA1IGFmdGVyIHRoYXQgc2VlbWluZyBleHBsYWluIGFsbW9zdCB0aGUgc2FtZSBhbW91bnQgb2YgdmFyaWFuY2UgYmV0d2VlbiB0aGVtIGFzIHRoZSBmaXJzdCBvbmUuIEkgZG9uJ3QgdGhpbmsgdXNpbmcganVzdCB0aGUgZmlyc3QgZWlnZW52YWx1ZSB3b3VsZCBwcm92aWRlIHRoYXQgbXVjaCBpbnNpZ2h0IGFuZCB0aGVyZWZvcmUgd2lsbCB1c2UgNiBvZiB0aGVtICh0aGlzIGlzIHN0aWxsIHJlZHVjaW5nIGRpbWVuc2lvbmFsaXR5IGJ5IGFsbW9zdCBoYWxmKS4KCmBgYHtyfQpucGNzID0gNgpgYGAKCldlIG5vdyBwbG90IHRoZSBQQ0EgdG8gdmlzdWFsaXNlIHRoZSBjbHVzdGVycyBmb3JtZWQgaGVyZS4gV2UncmUgbm90IHBsb3R0aW5nIGFjY29yZGluZyB0byBhbnkgY2F0ZWdvcmljYWwgZGF0YSBpLmUuIG5vcm1hbCB2cyBub24tbm9ybWFsIHNvIHdlIG1heSBub3QgZ2V0IHRoYXQgbXVjaCBpbmZvcm1hdGlvbiBmcm9tIHRoaXMuCgpgYGB7cn0KaT0xO2o9MgpwbG90KGRnX3RyYWluLnN2ZCR1WyxpXSwKICAgICBkZ190cmFpbi5zdmQkdVssal0sdHlwZT0icCIsCiAgICAgY29sPSIjMzMzMzMzMTEiLHBjaD0xNixjZXg9MSkKYGBgCgojIyBGaW5kaW5nIFBhcmFtZXRlcnMgZm9yIERCU0NBTgoKRXBzIHNwZWNpZmllcyBob3cgY2xvc2UgdGhlIHBvaW50cyBzaG91bGQgYmUgdG8gZWFjaCBvdGhlciB0byBmb3JtIGEgY2x1c3Rlci4gSWYgdGhlIGRpc3RhbmNlIGlzIGxlc3MgdGhhbiBlcHMsIHRoZXkgYXJlIGNvbnNpZGVyZWQgbmVpZ2hib3Vycy4gV2UgZmluZCB0aGlzIG51bWJlciBieSBmaW5kaW5nIHRoZSAna25lZScgaW4gdGhlIHBsb3QgYmVsb3cuIEkgaGF2ZSBjaG9zZW4gdG8gdXNlIDcgbmVpZ2hib3VycyBoZXJlLgoKYGBge3J9CnRlc3Q9a05OZGlzdChkZ190cmFpbi5zdmQkdVssMTpucGNzXSwgayA9IDcsYWxsPVRSVUUpCnRlc3RtaW49YXBwbHkodGVzdCwxLG1pbikKYGBgCgpgYGB7cn0KcGxvdChzb3J0KHRlc3RtaW5bdGVzdG1pbj4xZS04XSksbG9nPSJ5IikKdGhyZXNoaG9sZHM9IGMoMC4wMSwwLjAwMSwwLjAwMDEsMC4wMDAwMSwwLjAwMDAwMSkKYWJsaW5lKGg9YygwLjAxLDAuMDAxLDAuMDAwMSwwLjAwMDAxLDAuMDAwMDAxKSkKYWJsaW5lKGg9MC4wMDAxLCBjb2w9InJlZCIpCmBgYAoKU28gd2UgY2hvb3NlIGg9MC4wMDAxIGFzIG91ciBsaW1pdCBzaW5jZSB0aGlzIGFsbG93cyB1cyB0byBjYXB0dXJlIG1vc3Qgb2YgdGhlIGluZm9ybWF0aW9uIGhlcmUuIFdlIGFsc28gbmVlZCB0byBkZWZpbmUgb3VyIG1pbmltdW0gbnVtYmVyIG9mIHBvaW50cyB0byBmb3JtIGEgY2x1c3Rlci4gVGhlIHJlY29tbWVuZGF0aW9uIGlzIHRvIHVzZSBtaW5QdHMgPSAyKmRpbSBmb3IgbGFyZ2UgZGF0YSBzZXRzIHRvIGVuc3VyZSB3ZSBmaW5kIHNpZ25pZmljYW50IGNsdXN0ZXJzIGFuZCBhdm9pZCBub2lzZSBzbyB0aGlzIGlzIHdoYXQgd2Ugc2hhbGwgY2hvb3NlLgoKIyNEQlNDQU4KCk5vdyB3ZSBmaW5hbGx5IHBlcmZvcm0gREJTQ0FOLgoKYGBge3J9Cm1pblB0cyA9IGMoMjAsIDI1LCAzMCwgMzUsIDQwLCA0NSwgNTAsIDc1LCAxMDAsIDEyNSwgMTUwLCAxNzUsIDIwMCwgMjI1LCAyNTApCmNsdXN0ZXJjb3VudHMgPSBjKCkKCmZvcih2YWwgaW4gbWluUHRzKSB7CiAgZGJzY2FucmVzID0gZGJzY2FuKGRnX3RyYWluLnN2ZCR1WywxOjZdLGVwcyA9IDAuMDAwMSxtaW5QdHMgPSB2YWwpCiAgY2x1c3RlcmNvdW50c1t2YWxdIDwtIChsZW5ndGgodW5pcXVlKGRic2NhbnJlcyRjbHVzdGVyKSkpCn0KYGBgCgpgYGB7cn0KY2x1c3RlcmNvdW50cwpgYGAKClRodXMgd2Ugc2VlbSB0byBoaXQgc29tZSBsaW1pdGluZyB2YWx1ZSBhdCAxNzUgc2luY2UgYSBtaW5QdHMgb2YgMjAwIGhhcyBhIGhpZ2hlciBhbW91bnQgb2YgY2x1c3RlcnMgdGhhbiBhIG1pblB0cyBvZiAxNzUuIFNpbmNlIHdlIHdhbnQgb3UgZGF0YSB0byBiZSBpbnRlcnByZXRhYmxlIHdlIG1heSBsb29rIGF0IHJlZHVjaW5nIHRoZSBhbW91bnQgb2YgY2x1c3RlcnMgYW5kIHRoZXJlZm9yZSB0aGUgbm9pc2UuIFRodXMgd2Ugd2lsbCB1c2UgYW4gaW5pdGlhbCBtaW5QdHMgb2YgMTc1LgoKVGhlIG91dHB1dCB3ZSBnZXQgZnJvbSB0aGlzIGlzbid0IHZlcnkgaW5zaWdodGZ1bCB0aG91Z2ggYW5kIGxlYXZlcyBhIGxvdCB0byBiZSBkZXNpcmVkLiAKCmBgYHtyfQpkYnNjYW4xNzUgPSBkYnNjYW4oZGdfdHJhaW4uc3ZkJHVbLDE6Nl0sZXBzID0gMC4wMDAxLG1pblB0cyA9IDE3NSkKZGJzY2FuNTAgPSBkYnNjYW4oZGdfdHJhaW4uc3ZkJHVbLDE6Nl0sZXBzPTAuMDAwMSxtaW5QdHMgPSA1MCkKZGJzY2FuMzAgPSBkYnNjYW4oZGdfdHJhaW4uc3ZkJHVbLDE6Nl0sZXBzPTAuMDAwMSxtaW5QdHMgPSAzMCkKYGBgCgpgYGB7cn0KbGlicmFyeShjbHVzdGVyKQpgYGAKCmBgYHtyfQojIHRyeWluZyB0byBjYWxjdWxhdGUgdGhlIHNpbGhvdWV0dGUgc2NvcmUgb2YgdGhpcyBjbHVzdGVyaW5nIHRvIHNlZSBpZiBpdHMgdmFsaWQgb3Igbm90IC0gY3VycmVudGx5IHJlcG9ydHMgRXJyb3I6IFZlY3RvciBtZW1vcnkgZXhoYXVzdGVkIChsaW1pdCByZWFjaGVkPykgLSBJJ3ZlIHRyaWVkIGxvb2tpbmcgaW50byB3b3JrIGFyb3VuZHMgYnV0IGNhbnQgZ2V0IGFueXRoaW5nIHdvcmtpbmcgc28gSSdsbCBsZWF2ZSB0aGlzIGZvciBub3cuCiNzcyA8LSBzaWxob3VldHRlKGRic2NhbnJlcyRjbHVzdGVyLCBkaXN0KGRnX3RyYWluLnN2ZCR1KSkKYGBgCgojIyBQbG90dGluZyByZXN1bHRpbmcgY2x1c3RlcnMKCmBgYHtyfQpmb3IgKGsgaW4gMTo1KXsKICAgIGEgPSBzZXEoaysxLDYpCiAgICBmb3IgKGwgaW4gYSl7CiAgICAgICAgaWYoaz09bCl7bmV4dH0KICAgICAgICBwbG90KGRnX3RyYWluLnN2ZCR1WyxrXSwKICAgICAgICAgICAgZGdfdHJhaW4uc3ZkJHVbLGxdLHhsYWI9IiIsCiAgICAgICAgICAgIHlsYWI9IiIsCiAgICAgICAgICAgIGNvbD1jKCIjNjY2NjY2NjYiLHJhaW5ib3coNDEpKVtkYnNjYW4xNzUkY2x1c3RlcisxXSxwY2g9MTksY2V4PTAuNSkKICAgIHBhcihuZXc9VFJVRSkKICAgIH0KfQpgYGAKCmBgYHtyfQpmb3IgKGsgaW4gMTo1KXsKICAgIGEgPSBzZXEoaysxLDYpCiAgICBmb3IgKGwgaW4gYSl7CiAgICAgICAgaWYoaz09bCl7bmV4dH0KICAgICAgICBwbG90KGRnX3RyYWluLnN2ZCR1WyxrXSwKICAgICAgICAgICAgZGdfdHJhaW4uc3ZkJHVbLGxdLHhsYWI9IiIsCiAgICAgICAgICAgIHlsYWI9IiIsCiAgICAgICAgICAgIGNvbD1jKCIjNjY2NjY2NjYiLHJhaW5ib3coNDEpKVtkYnNjYW41MCRjbHVzdGVyKzFdLHBjaD0xOSxjZXg9MC41KQogICAgcGFyKG5ldz1UUlVFKQogICAgfQp9CmBgYAoKYGBge3J9CmZvciAoayBpbiAxOjUpewogICAgYSA9IHNlcShrKzEsNikKICAgIGZvciAobCBpbiBhKXsKICAgICAgICBpZihrPT1sKXtuZXh0fQogICAgICAgIHBsb3QoZGdfdHJhaW4uc3ZkJHVbLGtdLAogICAgICAgICAgICBkZ190cmFpbi5zdmQkdVssbF0seGxhYj0iIiwKICAgICAgICAgICAgeWxhYj0iIiwKICAgICAgICAgICAgY29sPWMoIiM2NjY2NjY2NiIscmFpbmJvdyg0MSkpW2Ric2NhbjMwJGNsdXN0ZXIrMV0scGNoPTE5LGNleD0wLjUpCiAgICBwYXIobmV3PVRSVUUpCiAgICB9Cn0KYGBgCgpgYGB7cn0KZm9yIChrIGluIDE6NSl7CiAgICBhID0gc2VxKGsrMSw2KQogICAgZm9yIChsIGluIGEpewogICAgICAgIGlmKGs9PWwpe25leHR9CiAgICAgICAgcGxvdChkZ190cmFpbi5zdmQkdVssa10sCiAgICAgICAgICAgIGRnX3RyYWluLnN2ZCR1WyxsXSx4bGFiPSIiLAogICAgICAgICAgICB5bGFiPSIiLAogICAgICAgICAgICBjb2w9YygiIzY2NjY2NjY2IixyYWluYm93KDQxKSlbZGJzY2FuMTc1JGNsdXN0ZXIrMV0scGNoPTE5LGNleD0wLjUpCiAgICB9Cn0KYGBgCgpgYGB7cn0KZm9yIChrIGluIDE6NSl7CiAgICBhID0gc2VxKGsrMSw2KQogICAgZm9yIChsIGluIGEpewogICAgICAgIGlmKGs9PWwpe25leHR9CiAgICAgICAgcGxvdChkZ190cmFpbi5zdmQkdVssa10sCiAgICAgICAgICAgIGRnX3RyYWluLnN2ZCR1WyxsXSx4bGFiPSIiLAogICAgICAgICAgICB5bGFiPSIiLAogICAgICAgICAgICBjb2w9YygiIzY2NjY2NjY2IixyYWluYm93KDQxKSlbZGJzY2FuNTAkY2x1c3RlcisxXSxwY2g9MTksY2V4PTAuNSkKICAgIH0KfQpgYGAKCmBgYHtyfQpmb3IgKGsgaW4gMTo1KXsKICAgIGEgPSBzZXEoaysxLDYpCiAgICBmb3IgKGwgaW4gYSl7CiAgICAgICAgaWYoaz09bCl7bmV4dH0KICAgICAgICBwbG90KGRnX3RyYWluLnN2ZCR1WyxrXSwKICAgICAgICAgICAgZGdfdHJhaW4uc3ZkJHVbLGxdLHhsYWI9IiIsCiAgICAgICAgICAgIHlsYWI9IiIsCiAgICAgICAgICAgIGNvbD1jKCIjNjY2NjY2NjYiLHJhaW5ib3coNDEpKVtkYnNjYW4zMCRjbHVzdGVyKzFdLHBjaD0xOSxjZXg9MC41KQogICAgfQp9CmBgYAoKCmBgYHtyfQpqcGVnKCJBc3Nlc3NtZW50MiBEQlNDQU4gQ2x1c3RlcmluZy5qcGciKQoKZm9yIChrIGluIDE6NSl7CiAgICBhID0gc2VxKGsrMSw2KQogICAgZm9yIChsIGluIGEpewogICAgICAgIGlmKGs9PWwpe25leHR9CiAgICAgICAgcGxvdChkZ190cmFpbi5zdmQkdVssa10sCiAgICAgICAgICAgIGRnX3RyYWluLnN2ZCR1WyxsXSx4bGFiPSIiLAogICAgICAgICAgICB5bGFiPSIiLAogICAgICAgICAgICBjb2w9YygiIzY2NjY2NjY2IixyYWluYm93KDQxKSlbZGJzY2FuMzAkY2x1c3RlcisxXSxwY2g9MTksY2V4PTAuNSkKICAgIHBhcihuZXc9VFJVRSkKICAgIH0KfQpkZXYub2ZmKCkKYGBgCgpgYGB7cn0KanBlZygiQXNzZXNzbWVudDIgREJTQ0FOIENsdXN0ZXJpbmcgRWlnZW52ZWN0b3Igc3BsaXQuanBnIikKb3AgPC0gcGFyKG1mcm93PWMoNSwzKSkKZm9yIChrIGluIDE6NSl7CiAgYSA9IHNlcShrKzEsNikKICBmb3IgKGwgaW4gYSl7CiAgICAgIGlmKGs9PWwpe25leHR9CiAgICAgIHBsb3QoZGdfdHJhaW4uc3ZkJHVbLGtdLAogICAgICAgICAgICBkZ190cmFpbi5zdmQkdVssbF0seGxhYj1rLAogICAgICAgICAgICB5bGFiPWwsCiAgICAgICAgICAgIGNvbD1jKCIjNjY2NjY2NjYiLHJhaW5ib3coNDEpKVtkYnNjYW4zMCRjbHVzdGVyKzFdLHBjaD0xOSxjZXg9MC41KQogICAgfQp9CnBhcihvcCkKZGV2Lm9mZigpCmBgYAoKYGBge3J9CmRnX3RyYWluLmNsdXN0ZXJlZCA8LSBkYXRhLmZyYW1lKGRnX3RyYWluKQoKZGdfdHJhaW4uY2x1c3RlcmVkJGNsdXN0ZXIgPC0gZGJzY2FuMTc1JGNsdXN0ZXIKCmRnX3RyYWluLmNsdXN0ZXJlZApgYGAKCiMjIE0gbWF0cml4CgpOb3cgd2UgbG9vayBhdCB0aGUgTSBtYXRyaXggcHJvZHVjZWQgYnkgQWxleCB0aGF0IGlzIGEgc3BhcnNlIG1hdHJpeCBzaG93aW5nIGNvbm5lY3Rpb25zIGJldHdlZW4gb3JpZ2luIElQJ3MgYW5kIHJlc3BvbnNlIElQJ3MuCgpgYGB7cn0KbGlicmFyeShNYXRyaXgpCmxpYnJhcnkoaXJsYmEpCmxpYnJhcnkoUnRzbmUpCmBgYAoKCmBgYHtyfQpTbzEgPC0gdGFwcGx5KG15ZGF0YSRpZC5vcmlnX2gsIG15ZGF0YSRpZC5vcmlnX2gpCkRlMSA8LSB0YXBwbHkobXlkYXRhJGlkLnJlc3BfaCwgbXlkYXRhJGlkLnJlc3BfaCkKRXN0IDwtIGFzLm1hdHJpeChjYmluZChTbzEsIERlMSkpCk08LSBzcGFyc2VNYXRyaXgoaT1Fc3RbLDFdLCBqPUVzdFssMl0pCmBgYAoKYGBge3J9Ck0uc3ZkID0gc3ZkKE0pCmBgYAoKYGBge3J9CnBsb3QoTS5zdmQkZCx4bGFiPSJFaWdlbnZhbHVlIGluZGV4Iix5bGFiPSJFaWdlbnZhbHVlIixsb2c9InkiKQpwbG90KE0uc3ZkJGQseGxhYj0iRWlnZW52YWx1ZSBpbmRleCIseWxhYj0iRWlnZW52YWx1ZSIpCmBgYAoKRnJvbSB0aGUgbG9nIGF4aXMgaXQgbG9va3MgbGlrZSB3ZSBuZWVkIHRoZSBmaXJzdCB+MTAwIGVpZ2VudmFsdWVzIGJ1dCB1c2luZyB0aGUgbm9ybWFsIHBsb3QsIGl0IGxvb2tzIGxpa2Ugd2UgYW4gZ2V0IGF3YXkgd2l0aCB1c2luZyB+MzAuCgpgYGB7cn0KbnBjc00gPSAzMApgYGAKCmBgYHtyfQp0ZXN0TT1rTk5kaXN0KE0uc3ZkJHVbLDE6bnBjc01dLCBrID0gNyxhbGw9VFJVRSkKdGVzdG1pbk09YXBwbHkodGVzdE0sMSxtaW4pCmBgYAoKYGBge3J9CnBsb3Qoc29ydCh0ZXN0bWluTVt0ZXN0bWluTT4xZS0xNV0pLGxvZz0ieSIpCnRocmVzaGhvbGRzPSBjKDAuMSwwLjAxLDAuMDAxLDAuMDAwMSwwLjAwMDAxLDAuMDAwMDAxKQphYmxpbmUoaD1jKDAuMDEsMC4wMDEsMC4wMDAxLDAuMDAwMDEsMC4wMDAwMDEpKQphYmxpbmUoaD0wLjUsIGNvbD0icmVkIikKYGBgCgpJdCBsb29rcyBsaWtlIHdlIHdhbnQgZXBzID0gMC41IGFsdGhvdWdoIHdlIGRvbnQgc2VlbSB0byBnZXQgYSBrbmVlIGluIHRoZSBkYXRhIHNvIGl0J3MgaGFyZCB0byBwaW5wb2ludCB0aGlzLgoKYGBge3J9Ck1taW5QdHMgPSBjKDIwMCkKY2x1c3RlcmNvdW50c00gPSBjKCkKCmZvcih2YWwgaW4gTW1pblB0cykgewogIGRic2NhbnJlc00gPSBkYnNjYW4oZGdfdHJhaW4uc3ZkJHVbLDE6Nl0sZXBzID0gMC41LG1pblB0cyA9IHZhbCkKICBjbHVzdGVyY291bnRzTVt2YWxdIDwtIChsZW5ndGgodW5pcXVlKGRic2NhbnJlc00kY2x1c3RlcikpKQp9CmBgYAoKYGBge3J9CmNsdXN0ZXJjb3VudHNNCmBgYAoKYGBge3J9CmRic2NhbjMwID0gZGJzY2FuKE4uc3ZkJHVbLDE6bnBjc01dLGVwcz0wLjUsbWluUHRzID0gMzApCmBgYAoKClJlZmVyZW5jZXM6CgoxLiBbRGF0YSBmcm9tIFNlY1JlcG9dKGh0dHBzOi8vd3d3LnNlY3JlcG8uY29tKQoKMi4gW0NvbnZlcnRpbmcgY2F0ZWdvcmljYWwgdmFyaWFibGVzXShodHRwczovL3N0YWNrb3ZlcmZsb3cuY29tL3F1ZXN0aW9ucy80NzkyMjE4NC9jb252ZXJ0LWNhdGVnb3JpY2FsLXZhcmlhYmxlcy10by1udW1lcmljLWluLXIvNDc5MjMxNzgpCgozLiBbQWRkaW5nIGNvbHVtbnMgdG8gZGF0YSBmcmFtZXNdKGh0dHBzOi8vZGlzY3Vzcy5hbmFseXRpY3N2aWRoeWEuY29tL3QvaG93LXRvLWFkZC1hLWNvbHVtbi10by1hLWRhdGEtZnJhbWUtaW4tci8zMjc4KQoKNC4gW0ZpbmRpbmcgVW5pcXVlIFZhbHVlc10oaHR0cHM6Ly9zdGFja292ZXJmbG93LmNvbS9xdWVzdGlvbnMvNDE5MDY4Nzgvci1udW1iZXItb2YtdW5pcXVlLXZhbHVlcy1pbi1hLWNvbHVtbi1vZi1kYXRhLWZyYW1lKQoKNS4gW0RCU0NBTiBvbiBmbG93ZXJzXShodHRwczovL3d3dy5nZWVrc2ZvcmdlZWtzLm9yZy9kYnNjYW4tY2x1c3RlcmluZy1pbi1yLXByb2dyYW1taW5nLykKCjYuIFtTYXZpbmcgUGxvdHNdKGh0dHA6Ly93d3cuc3RoZGEuY29tL2VuZ2xpc2gvd2lraS9jcmVhdGluZy1hbmQtc2F2aW5nLWdyYXBocy1yLWJhc2UtZ3JhcGhzKQoKNy4gW0RCU0NBTiBQYXJhbWV0ZXIgRXN0aW1hdGlvbl0oaHR0cHM6Ly9lbi53aWtpcGVkaWEub3JnL3dpa2kvREJTQ0FOI1BhcmFtZXRlcl9lc3RpbWF0aW9uKQoKOC4gW0ZpbmRpbmcgdGhlIGtuZWUgaW4ga05ORGlzdF0oaHR0cHM6Ly93d3cucmRvY3VtZW50YXRpb24ub3JnL3BhY2thZ2VzL2Ric2Nhbi92ZXJzaW9ucy8xLjEtNS90b3BpY3Mva05OZGlzdCkKCjkuIFtTaWxob3VldHRlIFNjb3JlIGludHJvZHVjdGlvbl0oaHR0cHM6Ly9tZWRpdW0uY29tL2NvZGVzbWFydC9yLXNlcmllcy1rLW1lYW5zLWNsdXN0ZXJpbmctc2lsaG91ZXR0ZS03OTQ3NzRiNDY1ODYpCgoxMC4gW0Vycm9yIHdpdGggc2lsaG91ZXR0ZSBzY29yZV0oaHR0cHM6Ly9zdGFja292ZXJmbG93LmNvbS9xdWVzdGlvbnMvNTEyNDgyOTMvZXJyb3ItdmVjdG9yLW1lbW9yeS1leGhhdXN0ZWQtbGltaXQtcmVhY2hlZC1yLTMtNS0wLW1hY29zKQoKMTEuIFtTaWxob3VldHRlIEZ1bmN0aW9uXShodHRwczovL3d3dy5yZG9jdW1lbnRhdGlvbi5vcmcvcGFja2FnZXMvY2x1c3Rlci92ZXJzaW9ucy8yLjEuMC90b3BpY3Mvc2lsaG91ZXR0ZSk=